package com.yaoli.niuke;

import com.yaoli.ajob.TreeNode;

/**
 * Created by siemens on 5/9/2017.
 */
public class _009_Test {
    public static void main(String[] args) {
//        TreeNode  a = new TreeNode(8);
//        TreeNode  b = new TreeNode(8);
//        TreeNode  c = new TreeNode(7);
//
//        TreeNode  d = new TreeNode(9);
//        TreeNode  e = new TreeNode(2);
//
//        TreeNode  f = new TreeNode(4);
//        TreeNode  g = new TreeNode(7);
//
//
//        a.setLeft(b);
//        a.setRight(c);
//
//        b.setLeft(d);
//        b.setRight(e);
//
//        e.setLeft(f);
//        e.setRight(g);
//
//        TreeNode  x = new TreeNode(8);
//        TreeNode  y = new TreeNode(9);
//        TreeNode  z = new TreeNode(2);
//
//        x.setLeft(y);
//        x.setRight(z);


        //{8,8,7,9,3,#,#,#,#,4,7},{8,9,2}

        TreeNode  a = new TreeNode(8);
        TreeNode  b = new TreeNode(8);
        TreeNode  c = new TreeNode(7);

        TreeNode  d = new TreeNode(9);
        TreeNode  e = new TreeNode(3);

        TreeNode  f = new TreeNode(4);
        TreeNode  g = new TreeNode(7);


        a.setLeft(b);
        a.setRight(c);

        b.setLeft(d);
        b.setRight(e);

        e.setLeft(f);
        e.setRight(g);

        TreeNode  x = new TreeNode(8);
        TreeNode  y = new TreeNode(9);
        TreeNode  z = new TreeNode(2);

        x.setLeft(y);
        x.setRight(z);


        _009_Test test = new _009_Test();
        System.out.println(test.HasSubtree(a,x));

    }

    boolean flag = false;
    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        if(root1 == null || root2 == null){
            return false;
        }
        calc(root2,root1);

        return flag;
    }

    public void calc(TreeNode tree,TreeNode node){
        if(node != null){
            boolean res = help(tree,node);
            if(res == true){
                flag = true;
                return;
            }
            calc(tree,node.left);
            calc(tree,node.right);
        }
    }

    public boolean help(TreeNode tree,TreeNode node){
        if(tree == null){
            return true;
        }else if(tree != null && node == null){
            return false;
        }else if(node != null && tree != null && node.val != tree.val){
            return false;
        }else if(node != null && tree != null && node.val == tree.val){

            boolean left = help(tree.left,node.left);
            boolean right = help(tree.right,node.right);

            if(left == true && right == true){
                return true;
            }else{
                return false;
            }

        }else{
            return true;
        }
    }
}
